1. Field of Invention
The present invention relates generally to network systems. More particularly, the present invention relates to enabling unicast and multicast connection requests to be routed through a Clos-like network such that bandwidth is preserved and utilized efficiently.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that more residential and business computer users are becoming connected to the Internet. Furthermore, the types of traffic being carried by the Internet are shifting from lower bandwidth applications towards high bandwidth applications which include voice traffic and video traffic.
Within a network, data may be transmitted between nodes, i.e., network elements such as switches. For example, data or information which originates at port associated with a source node may be routed to a port associated with a destination node. Often, the data may be routed through intermediate nodes. In other words, rather than being routed substantially directly from a source node to a destination node, data may be routed from the source node to at least one intermediate or center node before the data is routed to the destination node.
At times, data that is to be routed or transmitted may be blocked within a network. When blocking occurs in a network, data that is intended to be transmitted from one node to another node, e.g., via at least one center node, may be prevented from being successfully transmitted. As such, whenever possible, non-blocking networks are designed. In the design of non-blocking networks, Clos networks are widely used. A Clos network or matrix is generally a multi-stage interconnect in which each switch in each stage is connected to each switch in a successive stage by exactly one link. One particularly useful Clos network is a 3-stage symmetric Clos network which includes a first or input stage, a second or center stage, and a third or output stage.
In general, the non-blocking characteristic of a Clos network is dependent on the number of center stage nodes within the network. Two types of non-blocking Clos networks are a rearrangeable non-blocking network and a strictly non-blocking network. Rearrangeable non-blocking occurs when a desired connection is blocked when a current set of existing connections is in place, but the current set of existing connections within the network may be moved to different center stage nodes such that an appropriate center stage node may become available to facilitate the desired, e.g., new, connection. Typically, a rearrangeable non-blocking 3-stage network requires more center stage nodes than required by a blocking network. A strictly non-blocking network allows every requested connection to be made without having to rearrange a current set of existing connections. In order to implement a strictly non-blocking 3-stage network, a required number of center stage nodes is at least twice the number of input stage nodes, e.g., for a unicast request in a 3-stage Clos network, and may be much higher, e.g., for a multicast request in a 3-stage Clos network.
The number of center stage nodes needed to implement a strictly non-blocking network which supports multicast requests is often prohibitory and, hence, impractical to implement. As such, a rearrangeable non-blocking network may be implemented to support multicast requests, even though a rearrangeable non-blocking network may be slower than desired. A rearrangeable non-blocking network may enable the number of center stage nodes needed to support multicast requests to be reduced.
One solution to creating a non-blocking network involves a double-balancing technique as described in U.S. patent application Ser. No. 10/086,517, filed Feb. 28, 2002, and entitled “Multi-Stage Switching for Networks,” which is incorporated herein by reference in its entirety. Using a double-balancing technique, a substantially even distribution of load may be achieved within a network such as a six-chip network. FIG. 1 is a diagrammatic representation of a six-node or a six-chip network which supports mixed cast requests. A network 10 includes an input stage 14a which includes input stage nodes 18a, 18b. Network 10 also includes a center stage 14b which has center stage nodes 18c, 18d, as well as an output stage 14c which has output stage nodes 18e, 18f. Nodes 18a, 18b each have ‘n’ input ports 20, while nodes 18e, 18f each have ‘n’ output ports 24.
Nodes 18a, 18b are linked to nodes 18c, 18d by input stage to center stage links 22a-d, while nodes 18c, 18d are linked to nodes 18e, 18f by center stage to output stage links 22e-h. Each link 22 has a capacity defined as ‘n/2’. Further, each node 18a, 18b is connected to each node 18c, 18d by ‘n/2’ links 22, while each node 18c, 18d is connected to each node 18e, 18d by ‘n/2’ links 22. It should be appreciated that when there is exactly one link 22 between successive nodes 18, e.g., one link 22a between node 18a and node 18c as well as one link 22e between node 18c and node 18e, then network 10 is a Clos network.
By using a double-balancing algorithm or technique, a substantially even distribution of load across both input stage to center stage links 22a, 22b and center stage to output stage links 22c, 22d may be achieved. That is, an attempt is made to balance the load with respect to links 22 between input stage 14a and center stage 14b and with respect to links 22 between center stage 14b and output stage 14c. For multicast requests, the double-balancing algorithm picks a single center stage node 18c, 18d for use in routing a signal or information between an input port 20 and an output port 24.
As shown in FIG. 2, for a particular multicast request that is to reach output nodes 18e, 18f, a single center stage node 18c is chosen to provide the request to output nodes 18e, 18f. For clarity, links 22 which are not used to route the particular multicast request, input ports 20, and output ports 24 have not been shown in FIG. 2. When center stage node 18c is chosen to support a multicast request which is provided through input stage node 18a on link 22a, links 22e, 22f are used to pass the multicast request to output stage nodes 18e, 18f, respectively. Even in the event that links 22a, 22f, for example, may have less available capacity than links 22b, 22h of FIG. 1, links 22a, 22f may be used to route a multicast request when it is determined that overall, using center stage node 18c allows for a more even distribution of load than using center stage node 18d. 
If center stage 14b has some extra capacity, then the use of a single center stage node 18c, 18d to support multicast requests is generally effective in enabling a relatively even distribution of load to occur. When there is effectively no extra center stage capacity, and a multicast request has a fanout, then a limitation of having to route the request through a single center stage node 18c, 18d increases the chances of blocking. Multicast fanout is generally associated with the number of output nodes a given multicast request is destined to, and has a rate that may be a number between one and the total number of output nodes in a system. Hence, the overall performance associated with routing requests may be adversely affected by the lack of extra center stage capacity.
FIG. 3 is a process flow diagram which illustrates the steps associated with one method of routing requests through a Clos-like network such as network 10 of FIG. 1. A method 300 begins at step 304 in which a double-balancing algorithm is used to route requests through a common center node. Specifically, a double-balancing algorithm is used to route each unicast request through a center stage node that is deemed to be most suitable and to route each multicast request through a single center stage node.
When a new request, which may be a unicast request or a multicast request, is received in step 308, the new request is added into a table of requests in step 312, thereby updating the table of requests to include substantially all requests which are routed through the network. Once the table of requests is updated, then substantially all requests in the table of requests may effectively be rerouted in step 316 using a double-balancing algorithm. In other words, substantially every time a new request is received and added to the table of request, all requests in the table of requests are routed using a double-balancing algorithm in an effort to balance the load across all internal links of the network. Using a double balancing algorithm, center stage node candidates are selected by computing a cost which reflects the change in the utilization of links. For each request, the costs on the links between center stage and output stage nodes are computed for each center stage node. The node with the best cost is generally chosen for use in routing a request. When more than one candidate node is available, the cost on links between an input stage and the center stage are computed, and the candidate with the best associated cost is selected for use in routing the request. After all requests in the table of requests are routed, method 300 is completed.
In general, a double-balancing algorithm is effective in enabling mixed cast requests to be efficiently routed through a relatively small Clos-like network. However, as discussed above, the use of a double-balancing algorithm which uses a common center stage node to route a multicast request may sometimes result in a higher blocking rate, as for example when the Clos-like network is relatively large and only one center stage node may be used to route the request.
Some true Clos networks use multicast routing algorithms which use multiple center stage nodes, while trying to substantially minimize the number of center stage nodes used without significantly exceeding a desired blocking rate. Such algorithms are effective in routing multicast requests through a true Clos network, but are relatively ineffective in routing unicast requests. Hence, when a preponderance of requests to be routed through a true Clos network that supports mixed cast requests are unicast requests, such multicast routing algorithms result in relatively poor bandwidth utilization within the true Clos network. The poor performance in terms of bandwidth utilization may often be attributed to the fact that in a true Clos network, it is generally not possible to perform balancing, due to the fundamental nature of such a network. Since the link capacities are such that links are either available or not available, there is effectively no degree of availability associated with the links, which renders balancing to unbeneficial.
Therefore, what is needed is a method and an apparatus for minimizing the number of center stage nodes needed in a Clos-like network to achieve acceptable performance for both unicast and multicast requests. That is, what is desired is a system which enables mixed cast requests to be efficiently routed through a 3-stage Clos-like network with a substantially equal number of input nodes and center stage nodes such that an acceptable performance level, e.g., an acceptable blocking rate, is achieved.